Формула разбиений на k слагаемых

Пусть $P_k(n)$ — число разбиений $n$ на ровно $k$ слагаемых; тогда $P(n) = \sum\limits_{k=1}^n P_k(n)$

$$P_k(n) = P_{k-1}(n-1) + P_k(n-k)$$ при начальном условии $P_0(0) = 1$

!squares.svg Разбиение $n$ на $k$ слагаемых либо содержит слагаемое 1 (левая диаграмма), либо нет (правая). Если слагаемое 1 присутствует, мы его удаляем (закрашенный квадрат в первой строке). Остается разбиение числа $n-1$ на $k-1$ слагаемое. То есть $P_{k-1}(n-1)$ Если слагаемого 1 нет (все слагаемые $\geq 2$), то мы удаляем 1 из каждого из $k$ слагаемых (закрашенный первый столбец). Остается разбиение числа $n-k$ на $k$ слагаемых. То есть $P_{k}(n-k)$ $\square$